#include <iostream>
#include "sqlist.h"
#include <memory.h>

using namespace std;

Status InsertSort(SqList &);
Status SwapSort(SqList &);
Status SelectSort(SqList &);
Status MergeSort(SqList &, int start=-1, int end=-2);

int main(void)
{
	SqList sql;
	sql.InitList();
	int num[10], i;
	for(i = 0; i <= 9; i++)
		cin >> num[i];
	for(i = 0; i <= 9; i++)
		sql.ListInsert(num[i]);
	MergeSort(sql);
	for(i = 1; i <= 10; i++)
		printf("%d ", sql.GetElem(i));
	return 0;
}

Status InsertSort(SqList &L)
{
	int l = L.length, cur, i;
	ElemType dat;
	for(cur = 1; cur < l; cur++)
	{
		dat = L.elem[cur];
		for(i = cur-1; L.elem[i] >= dat && i >= 0; i--)
			L.elem[i+1] = L.elem[i];
		L.elem[i+1] = dat;
	}
	return OK;
}

Status SwapSort(SqList &L)
{
	int l = L.length, i, j;
	ElemType temp;
	for(i = 0; i < l-1; i++)
		for(j = i+1; j < l; j++)
			if(L.elem[i] > L.elem[j])
			{
				temp =L.elem[i];
				L.elem[i] = L.elem[j];
				L.elem[j] = temp;
			}
	return OK;
}

Status SelectSort(SqList &L)
{
	int l = L.length, i, j, min;
	ElemType temp;
	for(i = 0; i < l; i++)
	{
		min = i;
		for(j = i; j < l; j++)
			if(L.elem[j] < L.elem[min])
				min = j;
		temp = L.elem[i];
		L.elem[i] = L.elem[min];
		L.elem[min] = temp;
	}
	return OK;
}

Status MergeSort(SqList &L, int start, int end)
{
	if(start == -1 && end == -2)
	{
		start = 0;
		end = L.length-1;
	}
	else if(start == end)
		return OK;
	int mid = (start+end)/2, p1, p2,  p;

	MergeSort(L, start, mid);
	MergeSort(L, mid+1, end);

	ElemType *temp;
	temp = (ElemType *)malloc(sizeof(ElemType)*(end-start+1));
	p = 0;
	p1 = start;
	p2 = mid+1;
	while(p1 <= mid && p2 <= end)
	{
		if(L.elem[p1] < L.elem[p2])
			temp[p++] = L.elem[p1++];
		else
			temp[p++] = L.elem[p2++];
	}
	if(p1 > mid)
		while(p2 <= end)
			temp[p++] = L.elem[p2++];
	else if(p2 > end)
		while(p1 <= mid)
			temp[p++] = L.elem[p1++];
	for(int i = 0; i < end-start+1; i++)
		L.elem[start+i] = temp[i];
	free(temp);
	return OK;	
}